// https://leetcode.cn/problems/search-a-2d-matrix/description/

// 算法思路总结：
// 1. 将二维矩阵视为一维有序数组进行二分查找
// 2. 通过行列转换公式计算中间位置的元素值
// 3. 根据比较结果调整搜索区间边界
// 4. 检查最终位置是否匹配目标值
// 5. 时间复杂度：O(log(mn))，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) 
    {
        int m = matrix.size(), n = matrix[0].size();

        int l = -1, r = m * n;
        while (l + 1 != r)
        {
            int mid = (l + r) >> 1;
            int val = matrix[mid / n][mid % n];
            if (val == target)
            {
                return true;
            }
            else if (val < target)
            {
                l = mid;
            }
            else
            {
                r = mid;
            }
        }

        if (r < m * n && matrix[r / n][r % n] == target)
        {
            return true;
        }

        return false;
    }
};

int main()
{
    vector<vector<int>> matrix1 = {{1,3,5,7},{10,11,16,20},{23,30,34,60}};
    vector<vector<int>> matrix2 = {{1,3,5,7},{10,11,16,20},{23,30,34,60}};
    int target1 = 3, target2 = 13;

    Solution sol;

    cout << (sol.searchMatrix(matrix1, target1) == 1 ? "True" : "False") << endl;
    cout << (sol.searchMatrix(matrix2, target2) == 1 ? "True" : "False") << endl;

    return 0;
}